package LintCode;

import java.util.Arrays;

/**
 * @Classname FindKClosestElements
 * @Description TODO
 * @Date 2021/3/4 17:09
 * @Created by ASUS
 */
public class FindKClosestElements {
    /**
     * @param A:      an integer array
     * @param target: An integer
     * @param k:      An integer
     * @return: an integer array
     */
    public int[] kClosestNumbers(int[] A, int target, int k) {
        // write your code here

        // special case for directly return A
        if (A == null || A.length == 0) return A;
        if (k > A.length) return A;

        // 1. we need to find the value in A that closest to target with binary search method.
        int start = 0, end = A.length - 1, index, loss = Integer.MAX_VALUE;
        index = (start + end) >> 1;
        while (start < end - 1) {
            if (A[index] == target) break;
            else if (A[index] < target) start = index;
            else end = index;
            index = (start + end) >> 1;
        }
        index = Math.abs(A[index] - target) < Math.abs(A[index + 1] - target) ? index : index + 1;

        // create the answer array.
        int[] answer = new int[k];

        // 2. then we can enumerate k items and put them into the answer array.
        // in this part we need to clare special 2 cases : index is at the edge of A.
        start = index;
        end = index + 1;
        for (int i = 0; i < k; i++) {
            if (start < 0) answer[i] = A[end++];
            else if (end > A.length - 1) answer[i] = A[start--];
            else {
                if (target - A[start] <= A[end] - target) answer[i] = A[start--];
                else answer[i] = A[end++];
            }
        }
//        Arrays.sort(answer);
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new FindKClosestElements().kClosestNumbers(new int[]{1, 2, 3}, 2, 3)));
    }
}
